Object-oriented programming generally refers to a technology for, or way of writing, computer programs that encapsulates data to be operated on and the method(s) that operate on that data into a single entity referred to as an object. A definition of an object is typically referred to as a type or class, and a specific instance of a type or class is referred to as the object. This “creation” of an object is also referred to as instantiation of the type.
One benefit to object-oriented programming is that types can be created based on other types. A type can be defined as inheriting or deriving from another type, which allows the type to inherit all of the methods of that other (or “parent”) type. Thus, the type does not need to redefine all of the methods that were defined by the other type, rather it can simply inherit from that other type. This inheritance can result in a type inheritance hierarchy of two or more types (generally, there is no limit as to how many types can be in the inheritance hierarchy). For example, a first type can inherit from a second type, which can inherit from a third type, which can inherit from a fourth type. The first type then includes all of the methods that were defined by the second, third, and fourth types.
In addition to inheriting the methods of the other type, a type can also define new methods and override methods that were defined by the other type. For example, assume that there is a type “Shape” which defines a method “Draw” for drawing the shape and a method “Fill” for filling the shape with a texture. A type “Circle” can inherit from the type “Shape”, leave its “Fill” method unchanged, but override its “Draw” method to be specific instructions for drawing a circle in a particular way.
Methods that can be overridden are often referred to as “virtual methods” because the particular code that will be executed for such a method varies based on the type of the object in the inheritance hierarchy that the method is being called on. The determination of the appropriate code to execute when a virtual method is invoked is oftentimes referred to as “virtual method dispatching”. Typically, virtual method dispatching is handled using a “virtual table” or “vtable”. In a traditional virtual table, each method on a type is assigned a number starting from zero and monotonically increasing by one. The numbers assigned from previous types are maintained on a new type that derives from that previous type. For example, if a type defines two new methods and inherits from another type that had defined four methods (assigned numbers 0, 1, 2, and 3), the two new methods on the type would be assigned numbers 4 and 5.
The virtual table has a series of pointers in it that each point to code to be executed in order to carry out one of the methods on an object. These pointers are in the same order as the numbers assigned to the methods of the object's type. For example, if the third method on a type “Shape” is the “Draw” method and is assigned the number 2, then the third pointer in the series of pointers is the pointer to the code to be executed in order to carry out the “Draw” method on an object of type “Shape.”
When a type overrides a method on another type, the type adheres to this numbering scheme and order of pointers in the series of pointers. The type simply changes the pointer at the proper location in the series of pointers to point to the new code that the type is using for the method. Following the previous example, if a type “Circle” inherited from the type “Shape” and desired to override the “Draw” method, then the third pointer in the series of pointers would be changed to point to the new code to be executed in order to carry out the “Draw” method on an object of type “Circle.” By having all types in the type inheritance hierarchy adhere to this same numbering scheme, the methods on all of the types can be easily invoked. For example, the “Draw” method would always be assigned the number 2, regardless of which object type in the hierarchy the method was being called on, and regardless of how many times (if any) the method had been overridden.
One problem with these traditional virtual tables is the storage space that they require. When a type inherits from another type, it copies all of the methods from that other type, which can result in a large number of methods. So, for example, if a first type defines 10 methods, a second type inherits from the first type and defines 10 additional methods, a third type inherits from the second type and defines yet another 10 additional methods, and a fourth type inherits from the third type and defines still another 10 methods, then the fourth type has 40 methods defined on it, the third type has 30 methods defined on it, the second type has 20 methods defined on it, and the first type has 10 methods defined on it. There are only 40 total methods, but with all four types defined there are 100 method pointers stored (40+30+20+10). This problem is only exacerbated as type inheritance hierarchies grow longer.
A particularly troublesome issue with the size of such virtual tables is the situation where only a couple of the methods are commonly used. Thus, following the previous example, if only two methods on the fourth type are commonly used, then a significant amount of storage space is being devoted to methods that are not being used (that is, the storage space required for the 38 out of 40 methods not commonly being used).
Thus, it would be beneficial to have a way to reduce the storage space requirements for virtual method dispatching.